package previous.Test_0330;

import java.util.*;

/**
 * Created with Intellij IDEA
 * Description:
 * User: 星辰
 */
public class Solution {
    //01背包
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        int n=scan.nextInt();
        int V=scan.nextInt();
        int[] v=new int[n+1];
        int[] w=new int[n+1];
        for (int i = 1; i <= n; i++) {
            v[i]=scan.nextInt();//体积
            w[i]=scan.nextInt();//价值
        }
        //dp[i][j]:从前i个物品中挑选，总体积不超过j，所能选中的最大价值
        int[][] dp=new int[n+1][V+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=V; j++) {
                dp[i][j]=dp[i-1][j];
                //如果大于，能放入
                if(j>=v[i]) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-v[i]]+w[i]);
            }
        }
        int max1=dp[n][V];
        int[][] dp2=new int[n+1][V+1];
        for (int i = 1; i <=V; i++) {
            dp2[0][i]=-1;
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=V ; j++) {
                dp2[i][j]=dp2[i-1][j];
                //如果大于，能放入
                if(j>=v[i] && dp2[i-1][j-v[i]]!=-1)
                    dp2[i][j]=Math.max(dp2[i][j],dp2[i-1][j-v[i]]+w[i]);
            }
        }
        int max2=dp2[n][V]==-1?0:dp2[n][V];
        System.out.println(max1);
        System.out.println(max2);
    }
    //分割等和子集
    public boolean canPartition(int[] nums) {
          int n=nums.length;
          int sum=0;
        for (int i = 0; i < n; i++) {
            sum+=nums[i];
        }
        if(sum%2==1) return false;
        sum/=2;
        boolean[][] dp=new boolean[n+1][sum+1];
        for (int i = 0; i <= n; i++) {
            dp[i][0]=true;
        }
        for (int i = 1; i <=n ; i++) {
            for (int j = 1; j <=sum ; j++) {
                dp[i][j]=dp[i-1][j];
                if(j>=nums[i-1]){
                    dp[i][j]=dp[i][j] || dp[i-1][j-nums[i-1]];
                }
            }
        }
        return dp[n][sum];
    }

    //最后一块石头的重量
    public int lastStoneWeightII(int[] stones) {
          int n=stones.length;
          int sum=0;
          for(int x:stones) sum+=x;
          int aim=sum/2;
          int[][] dp=new int[n+1][aim+1];
        for (int i = 1; i <=n ; i++) {
            for (int j = 0; j <=aim; j++) {
                dp[i][j]=dp[i-1][j];
                if(j>=stones[i-1])
                    dp[i][j]=Math.max(dp[i][j],dp[i-1][j-stones[i-1]]+stones[i-1]);
            }
        }
        return sum-2*dp[n][aim];
    }
}
